//链表实现栈
struct LinkList
{
    int index;

    LinkList* next;
    LinkList* pre;
};

LinkList* newLinkList(int value)
{
    LinkList* newItem=new LinkList;
    newItem->index=value;
    newItem->next=NULL;
    newItem->pre=NULL;
    return newItem;
}

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//链表添加新的节点
LinkList* addItem(LinkList* l,LinkList* newItem)
{
    if(l==NULL)
    {
        l=newItem;   
    }
    else{
        l->next=newItem;
        newItem->pre=l;
    }
    return newItem;
}

//无限长度的栈 必须要用链表实现
struct Stack
{
    LinkList* start; //队列起点
    LinkList* end;   //队列终点
    int size;//队列元素个数
};

Stack* newStack(){
    Stack* stack=new Stack;
    stack->start=NULL;
    stack->end=NULL;
    stack->size=0;
    return stack;
}

//清空队列
void deleteStack(Stack* s)
{
    deleteLinkList(s->start);
    delete s;
}

//入栈
void pushStack(Stack* s,LinkList* item)
{
    LinkList* end=addItem(s->end,item);
    s->end=end;
    if(s->start==NULL)
    {
        s->start=end;
    }
    s->size++;
}

//出栈
LinkList* popStack(Stack* s){
    if(s->end==NULL)
    {
        return NULL;
    }
    else{
        LinkList* end=s->end;
        s->end=s->end->pre;
        if(s->end==NULL)
        {
            s->start=NULL;
        }
        else{
            s->end->next=NULL;
        }

        s->size--;
        end->pre=NULL;
        return end;
    }
}

//栈元素多少
int sizeOfStack(Stack* s)
{
    return s->size;
}

//栈是否为空
int isEmpStack(Stack* s)
{
    return s->size<=0;
}